#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    void nextPermutation(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		if(num.size()<=1)
			return;

		size_t count = num.size();
		size_t maxR = -1;
		for(size_t i=0;i<(count-1);i++)
		{
			if(num[i]<num[i+1])
			{
				maxR = i;
			}
		}

		if(maxR == -1)
		{
			sort(num.begin(),num.end());
		}
		else
		{
			size_t curR = maxR;
			for(size_t i = maxR+1;i<count;i++)
			{
				if(num[i]<=num[curR])
				{
					maxR = i-1;
					break;
				}
			}

			if(maxR==curR)
				maxR = count-1;

			swap(num[curR],num[maxR]);
			size_t i=curR+1, j = num.size()-1;
			while(i<j)
			{
				swap(num[i],num[j]);
				i++,j--;
			}
		}
    }
};
#endif